package com.origin.niuke;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/17 22:14
 * 算法：贪心
 * 一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
 * 1. 每个孩子不管得分多少，起码分到一个糖果。
 * 2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
 * 给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。
 * 先从左往右遍历，如果右边的得分大于左边的得分，那么 +1；从左往右最大的递增量
 * 从右往左遍历，如果左边的得分大于右边的得分，那么 +1 或者不变，取最大的那个；从右往做最大的递增量
 */
public class 分糖果问题 {

    public int candy(int[] arr) {
        int n = arr.length;
        if (n <= 1) return n;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        for (int i = 1; i < n; i++) if (arr[i] > arr[i - 1]) candies[i] = candies[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--)
            if (arr[i] > arr[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        int ans = 0;
        for (int candy : candies) ans += candy;
        return ans;
    }

}
